<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <title>封装树结构</title>
  </head>
  <body>
    <script type="text/javascript">
      // 创建BinarySearchTree
      function BinarySerachTree() {
        // 创建结点构造函数
        function Node(key) {
          this.key = key
          this.left = null
          this.right = null
        }

        // 保存根的属性
        this.root = null

        // 二叉搜索树相关的操作方法

        // 1.insert(key)：向树中插入一个新的键。
        BinarySerachTree.prototype.insert = function(key) {
          // 1.根据key创建对应的node
          let newNode = new Node(key)
          // 2.判断根结点是否有值
          if (this.root === null) {
            this.root = newNode
          } else {
            this.insertNode(this.root, newNode)
          }
        }

        // 2.insertNode方法 递归循环比较
        BinarySerachTree.prototype.insertNode = function(node, newNode) {
          if (newNode.key < node.key) { // 1.准备向左子树插入数据
            if (node.left === null) { // 1.1.node的左子树上没有内容
              node.left = newNode
            } else { // 1.2.node的左子树上已经有了内容
              this.insertNode(node.left, newNode)
            }
          } else { // 2.准备向右子树插入数据
            if (node.right === null) { // 2.1.node的右子树上没有内容
              node.right = newNode
            } else { // 2.2.node的右子树上有内容
              this.insertNode(node.right, newNode)
            }
          }
        }

        //2. 遍历二叉搜索树

        // 1.先序遍历
       BinarySerachTree.prototype.preOrderTraversal = function (handler) {
           this.preOrderTranversalNode(this.root, handler)
       }
       
       BinarySerachTree.prototype.preOrderTranversalNode = function (node, handler) {
           if (node !== null) {
               // 1.打印当前经过的节点
               handler(node.key)
               // 2.遍历所有的左子树
               this.preOrderTranversalNode(node.left, handler)
               // 3.遍历所有的右子树
               this.preOrderTranversalNode(node.right, handler)
           }
       }

        // 2.中序遍历
        BinarySerachTree.prototype.inOrderTraversal = function(handler) {
          this.inOrderTraversalNode(this.root, handler)
        }

        BinarySerachTree.prototype.inOrderTraversalNode = function(node, handler) {
          if (node !== null) {
            this.inOrderTraversalNode(node.left, handler)
            handler(node.key)
            this.inOrderTraversalNode(node.right, handler)
          }
        }

        // 3.后续遍历
        BinarySerachTree.prototype.postOrderTraversal = function(handler) {
          this.postOrderTraversalNode(this.root, handler)
        }

        BinarySerachTree.prototype.postOrderTraversalNode = function(node, handler) {
          if (node !== null) {
            this.postOrderTraversalNode(node.left, handler)
            this.postOrderTraversalNode(node.right, handler)
            handler(node.key)
          }
        }

        // 3.最小值
        BinarySerachTree.prototype.min = function() {
          let node = this.root
          while (node.left !== null) {
            node = node.left
          }
          return node.key
        }

        // 4.最大值
        BinarySerachTree.prototype.max = function() {
          let node = this.root
          while (node.right !== null) {
            node = node.right
          }
          return node.key
        }

        //5.search方法查找
        BinarySerachTree.prototype.search = function(Key) {
          let node = this.root
          while (node !== null) {
            if (node.key > Key) {
              node = node.left
            } else if ((node.key < Key)) {
              node = node.right
            } else {
              return true
            }
          }
          return false
        }
        //6.remove方法删除结点
        BinarySerachTree.prototype.remove = function(key) {
          // 1.寻找要删除的节点
          // 1.1定义变量
          let current = this.root // 要删除的节点
          let parent = null // 要删除节点的父节点
          let isLeftChild = true // 记录我们是在current是在父节点的左侧还是右侧
          // 1.2开始循环遍历      记录删除节点是在左侧还是右侧 
          while (current.key !== key) {
            parent = current
            if (key < current.key) {   
              isLeftChild = true       //说明current在父节点左侧
              current = current.left
            } else {
              isLeftChild = false        //说明current在父节点右侧
              current = current.right
            }
            if (current === null) return false
          }
          // 2.根据对应的情况删除节点
          // 情况一: 没有子节点
          if (current.left === null && current.right === null) {
            if (current == this.root) {
              this.root = null
            } else if (isLeftChild) {
              parent.left = null
            } else {
              parent.right = null
            }
          }
          // 情况二: 一个子节点
          else if (current.right === null) {
            if (current == this.root) {
              this.root = current.left
            } else if (isLeftChild) {
              parent.left = current.left
            } else {
              parent.right = current.left
            }
          } else if (current.left === null) {
            if (current == this.root) {
              this.root = current.right
            } else if (isLeftChild) {
              parent.left = current.right
            } else {
              parent.right = current.right
            }
          }
          // 情况三: 两个子节点
          else {
            // 1.获取后继节点
            let successor = this.getSuccessor(current)

            // 2.判断是否是根节点
            if (current == this.root) {
              this.root = successor
            } else if (isLeftChild) {
              parent.left = successor
            } else {
              parent.right = successor
            }

            // 3.将删除节点的左子树赋值给successor
            successor.left = current.left
          }
          return true
        }
        // 找后继的方法
        BinarySerachTree.prototype.getSuccessor = function (delNode) {
            // 1.使用变量保存临时的节点
            let successorParent = delNode
            let successor = delNode
            let current = delNode.right // 要从右子树开始找
        
            // 2.寻找后继节点
            while (current != null) {
                successorParent = successor
                successor = current
                current = current.left
            } 
        
            // 3.判断寻找到的后继节点是否直接是delNode的right节点
            if (successor != delNode.right) {
                successorParent.left = successor.right
                successor.right = delNode.right
            }
            
            return successor
        }
      }

      // 测试代码
      let bst = new BinarySerachTree()

      // 1.插入数据
      bst.insert(11)
      bst.insert(7)
      bst.insert(15)
      bst.insert(5)
      bst.insert(3)
      bst.insert(9)
      bst.insert(8)
      bst.insert(10)
      bst.insert(13)
      bst.insert(12)
      bst.insert(14)
      bst.insert(20)
      bst.insert(18)
      bst.insert(25)

     //2. 遍历二叉搜索树
      // 1.先序遍历
      let resultString = ""
      bst.preOrderTraversal(function(key){
        resultString += key + " "
      })
      alert(resultString)  // 11 7 5 3 9 8 10 15 13 12 14 20 18 25  
      // 2.中序遍历=
      resultString = ""
      bst.inOrderTraversal(function(key) {
        resultString += key + " "
      })
      alert(resultString) // 3 5 7 8 9 10 11 12 13 14 15 18 20 25 

      // 3.后续遍历
      resultString = ""
      bst.postOrderTraversal(function(key) {
        resultString += key + " "
      })
      alert(resultString) // 3 5 8 10 9 7 12 14 13 18 25 20 15 11 
      // 3.获取最小值
      alert(bst.min()) // 3
      // 4.获取最大值
      alert(bst.max()) // 25

      // 5.search方法
      alert(bst.search(10)) // true
      alert(bst.search(21)) // false
    </script>
  </body>
</html>
